package net.sf.nlp.ltag.parser;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Iterator;
import java.util.List;

import net.sf.nlp.ltag.data.ArrayKey;
import net.sf.nlp.ltag.data.LTAGNode;
import net.sf.nlp.ltag.data.LTAGStatistics;
import net.sf.nlp.ltag.data.LTAGTree;
import net.sf.nlp.ltag.data.Operator;
import net.sf.nlp.ltag.data.Word;

public class LTAGState implements Cloneable, Comparable<LTAGState>{
	
	protected long id;
	
	protected LTAGTree tree;
	protected LTAGNode node;
	
	protected LTAGState previousState = null;
	private LTAGState parentState = null;
	
	private ArrayList<Operator> operatorHistory = new ArrayList<Operator>();
	private Operator[] operatorArray = null;
	protected ArrayList<LeafNode> parsedLeafNodes = new ArrayList<LeafNode>();
	
	private double freq = Double.MAX_VALUE;
	//private double adjunctionFreq = Double.MAX_VALUE;
	
	public LTAGState(LTAGTree tree)
	{
		this.tree = tree;
		this.node = tree.getRoot();
		
		if (parsedLeafNodes.size() == 0)
		{
			buildParsedLeafNodes();
			initFreq();
		}
	}
	public long getId() {
		return id;
	}

	public void setId(long id) {
		this.id = id;
	}
	public LTAGTree getTree() {
		return tree;
	}
	public void setTree(LTAGTree tree) {
		this.tree = tree;
	}
	public LTAGNode getNode() {
		return node;
	}
	public void setNode(LTAGNode node) {
		this.node = node;
	}
	public LTAGState getPreviousState() {
		return previousState;
	}
	public void setPreviousState(LTAGState previousState) {
		this.previousState = previousState;
	}
	public LTAGState getParentState() {
		return parentState;
	}
	public void setParentState(LTAGState parentState) {
		this.parentState = parentState;
	}
	public ArrayList<Operator> getOperatorHistory() {
		return operatorHistory;
	}
	public void setOperatorHistory(ArrayList<Operator> operatorHistory) {
		this.operatorHistory = operatorHistory;
	}

	public Operator[] getOperatorArray() {
		if (operatorArray == null)
			operatorArray = operatorHistory.toArray(new Operator[]{});
		
		return operatorArray;
	}
	public void setParsedLeafNodes(ArrayList<LeafNode> parsedLeafNodes) {
		this.parsedLeafNodes = parsedLeafNodes;
	}
	
	public double getFreq() {
		return freq;
	}
	public void setFreq(double freq) {
		this.freq = freq;
	}

	private void initFreq()
	{
		freq = LTAGStatistics.getStatistics(LTAGStatistics.buildKey4BeginingTree(tree));
	}
	
	public void addNoAdjunctionFreq()
	{
		LTAGNode previousNode = tree.getNodeByLocation(node.getLocation() - 1);
		
		if (previousNode == null)
			return;
		
		if (previousNode.getLeafIndex() != -1)
			return;
		
		boolean adjuncted = false;
		for (Operator operator : operatorHistory)
		{
			if (tree != operator.getTree1())
				continue;
			
			if (previousNode == operator.getTree1Node())
			{
				adjuncted = true;
				break;
			}
		}
		
		if (adjuncted)
			return;
		
		ArrayKey key = LTAGStatistics.buildKey4NoAdjunction(tree, previousNode);
		
		freq = freq + LTAGStatistics.getStatistics(key);
	}
	
	public void addOperator(Operator operator)
	{
		operatorHistory.add(operator);
		
		if (operatorHistory.size() == 1)
		{
			ArrayKey key = LTAGStatistics.buildKey4BeginingTree(operator.getTree1());
			freq = LTAGStatistics.getStatistics(key);
		}
		
		ArrayKey key = LTAGStatistics.buildKey4Operator(operator);
		
		freq = freq + LTAGStatistics.getStatistics(key);
	}
	
	public int getStep()
	{
		int step = 0;
		
		Iterator<LeafNode> it = parsedLeafNodes.iterator();
		while (it.hasNext())
		{
			Word word = it.next().getLeafNode().getWord();
			
			if (word == null)
				break;
			
			if (word.getWordIndex() != step)
				break;
			
			step++;
		}
		
		return step;
	}
	
	public int getNearWordIndex()
	{
		int nearWordIndex = -1;
		
		Iterator<LeafNode> it = parsedLeafNodes.iterator();
		while (it.hasNext())
		{
			Word word = it.next().getLeafNode().getWord();
			
			if (word == null)
				continue;
			
			if (word.getWordIndex() > this.getTree().getWordIndex() &&
				(nearWordIndex == -1 || nearWordIndex > word.getWordIndex()))
				nearWordIndex = word.getWordIndex();
		}
		
		return nearWordIndex;
	}
	
	public boolean isMatched(List<Word> words)
	{
		if (parsedLeafNodes.size()!= words.size())
			return false;
		
		Iterator<LeafNode> it = parsedLeafNodes.iterator();
		
		while (it.hasNext())
		{
			LeafNode leafNode = it.next();
			
			if (leafNode.getLeafNode().getWord() == null)
				return false;
		}
		
		return true;
	}
	
	public boolean validateOperator(List<Word> words)
	{
		buildParsedLeafNodes();
		
		if (parsedLeafNodes.size() > words.size())
			return false;
		
		int preWordIndex = -1;
		int candidateNodesCount = 0;
		Iterator<LeafNode> it = parsedLeafNodes.iterator();
		
		while (it.hasNext())
		{
			LeafNode leafNode = it.next();
			Word word = leafNode.getLeafNode().getWord();
			
			if (word == null)
			{
				candidateNodesCount++;
				continue;
			}
			
			if (word.getWordIndex() - preWordIndex <= candidateNodesCount)
				return false;
			
			preWordIndex = word.getWordIndex();
			candidateNodesCount = 0;
		}
		
		return true;
	}
	
	private void buildParsedLeafNodes()
	{
		if (operatorHistory.size() == 0)
		{
			List<LTAGNode> treeLeafNodes = tree.getLeafNodes();
			
			for (LTAGNode treeLeafNode : treeLeafNodes)
				parsedLeafNodes.add(new LeafNode(tree, treeLeafNode));
		}
		else
		{
			Operator lastOperator = operatorHistory.get(operatorHistory.size() - 1);
			String op = lastOperator.getOperator();
			
			if ("$".equals(op))
				buildParsedLeafNodesForSubsititution(lastOperator);
			else if ("*".equals(op))
				buildParsedLeafNodesForAdjunct(lastOperator);
		}
	}
	
	private void buildParsedLeafNodesForSubsititution(Operator lastOperator)
	{
		int index = 0;
		LTAGTree tree2 = lastOperator.getTree2();
		LTAGNode tree1Node = lastOperator.getTree1Node();
		List<LTAGNode> tree2LeafNodes = tree2.getLeafNodes();
		
		for (; index < parsedLeafNodes.size(); index++)
		{
			LeafNode leafNode = parsedLeafNodes.get(index);
			LTAGNode node = leafNode.getLeafNode();
			
			if (node == tree1Node)
				break;
		}
		
		parsedLeafNodes.remove(index);
		
		for (int j = tree2LeafNodes.size() - 1; j >=0; j--)
			parsedLeafNodes.add(index, new LeafNode(tree2, tree2LeafNodes.get(j)));		
	}
	
	private void buildParsedLeafNodesForAdjunct(Operator lastOperator)
	{
		LTAGTree tree2 = lastOperator.getTree2();
		List<LTAGNode> tree2LeafNodes = tree2.getLeafNodes();
		
		List<LeafNode> adjunctImpactedNodes = new ArrayList<LeafNode>();
		int[] range = getImpactAdjunctNodeRange(lastOperator);
		int start = range[0];
		int end = range[1];
		
		for (int index = end; index >=start ; index--)
		{
			LeafNode leafNode = parsedLeafNodes.remove(index);
			adjunctImpactedNodes.add(0, leafNode);
		}
		
		for (int j = tree2LeafNodes.size() - 1; j >=0; j--)
		{
			LTAGNode tree2LeafNode = tree2LeafNodes.get(j);
			
			if ("*".equals(tree2LeafNode.getType()))
				parsedLeafNodes.addAll(start, adjunctImpactedNodes);
			else
				parsedLeafNodes.add(start, new LeafNode(tree2, tree2LeafNodes.get(j)));
		}
	}
	
	private int[] getImpactAdjunctNodeRange(Operator lastOperator)
	{
		int start = Integer.MAX_VALUE;
		int end = Integer.MIN_VALUE;
		
		List<LTAGNode> impactNodes = new ArrayList<LTAGNode>();
		LTAGTree tree1 = lastOperator.getTree1();
		LTAGNode tree1Node = lastOperator.getTree1Node();
		
		impactNodes.addAll(tree1Node.getLeafNodes());
		
		for (int i = operatorHistory.size() - 2; i >= 0; i--)
		{
			Operator operator = operatorHistory.get(i);
			
			if (!"*".equals(operator.getOperator()))
				break;
			if (tree1 != operator.getTree2())
				break;
			
			tree1Node = operator.getTree1Node();
			impactNodes.addAll(tree1Node.getLeafNodes());
			
			tree1 = operator.getTree1();
		}
		
		for (LTAGNode impactNode : impactNodes)
		{
			if ("*".equals(impactNode.getType()))
				continue;
			
			int index = indexOfParsedLeafNode(impactNode);
			
			if (start > index)
				start = index;
			if (end < index)
				end = index;
		}
		
		return new int[]{start, end};
	}
	
	private int indexOfParsedLeafNode(LTAGNode node)
	{
		int size = parsedLeafNodes.size();
		
		for (int i = 0; i < size; i++)
		{
			LeafNode parsedLeafNode = parsedLeafNodes.get(i);
			
			if (parsedLeafNode.getLeafNode() == node)
				return i;
		}
		
		return -1;
	}

	/*
	private void buildParsedLeafNodesForAdjunct(Operator lastOperator)
	{
		int start = -1;
		int end = -1;
		LTAGTree tree1 = lastOperator.getTree1();
		LTAGTree tree2 = lastOperator.getTree2();
		LTAGNode tree1Node = lastOperator.getTree1Node();
		List<LTAGNode> tree2LeafNodes = tree2.getLeafNodes();
		
		for (int index = 0; index < parsedLeafNodes.size(); index++)
		{
			LeafNode leafNode = parsedLeafNodes.get(index);
			
			//if (tree1 != leafNode.getTree())
			//	continue;
			//LTAGNode node = leafNode.getLeafNode();
			
			LTAGNode node = getImpactAdjunctNode(tree1, leafNode);
			
			while (node != null)
			{
				if (node == tree1Node)
				{
					if (start == -1)
					{
						start = index;
						end = index;
					}
					else
						end = index;
					
					break;
				}
				
				node = node.getParent();
			}
		}
		
		int[] range = getImpactAdjunctNodeRange(lastOperator);
		
		if (start != range[0] || end != range[1])
			System.out.println("debug");
		
		List<LeafNode> adjunctImpactedNodes = new ArrayList<LeafNode>();
		
		for (int index = end; index >=start ; index--)
		{
			LeafNode leafNode = parsedLeafNodes.remove(index);
			adjunctImpactedNodes.add(0, leafNode);
		}
		
		for (int j = tree2LeafNodes.size() - 1; j >=0; j--)
		{
			LTAGNode tree2LeafNode = tree2LeafNodes.get(j);
			
			if ("*".equals(tree2LeafNode.getType()))
				parsedLeafNodes.addAll(start, adjunctImpactedNodes);
			else
				parsedLeafNodes.add(start, new LeafNode(tree2, tree2LeafNodes.get(j)));
		}
	}
	
	private LTAGNode getImpactAdjunctNode(LTAGTree adjunctTree, LeafNode leafNode)
	{
		LTAGTree tree = leafNode.getTree();
		LTAGNode node = leafNode.getLeafNode();
		
		if (adjunctTree == tree)
			return leafNode.getLeafNode();
		
		for (int i = operatorHistory.size() - 2; i >= 0; i--)
		{
			Operator operator = operatorHistory.get(i);
			
			if (!"*".equals(operator.getOperator()))
				continue;
			if (tree != operator.getTree1())
				continue;
			
			if (adjunctTree != operator.getTree2() && node.isChildOfNode(operator.getTree1Node()))
			{
				tree = operator.getTree2();
				node = tree.getFoot();
			}
			else if (node.isChildOfNode(operator.getTree1Node()))
			{
				return adjunctTree.getFoot();
			}
		}
		
		return null;
	}
	*/
	public String toString()
	{
		StringBuffer sb = new StringBuffer();
		
		sb.append(id).append(".");
		sb.append("[");
		sb.append(tree.getRoot().getNodeText());
		if (tree.getId() != null)
			sb.append("-").append(tree.getId());
		sb.append(", ");
		sb.append(node.getNodeText());
		sb.append("(").append(node.getLocation()).append(")");
		if (node.getWord() != null)
			sb.append("#").append(node.getWord().getLexical());
		sb.append("]");
		
		sb.append("(");
		if (previousState != null)
			sb.append(previousState.getId());
		else
			sb.append("");
		sb.append("->").append(id).append(")");
		
		return sb.toString();
	}
	
	public LTAGState clone()
	{
		LTAGState clone = null;
		
		try 
		{
			clone = (LTAGState)super.clone();
			clone.setOperatorHistory(cloneOperatorHistory());
			clone.setParsedLeafNodes(cloneParsedLeafNodes());
		} 
		catch (CloneNotSupportedException e) 
		{
			e.printStackTrace();
		}
		
		return clone;
	}
	
	public LTAGState simpleClone()
	{
		LTAGState clone = null;
		
		try 
		{
			clone = (LTAGState)super.clone();
		} 
		catch (CloneNotSupportedException e) 
		{
			e.printStackTrace();
		}
		
		return clone;
	}
	
	@SuppressWarnings("unchecked")
	public ArrayList<Operator> cloneOperatorHistory()
	{
		return (ArrayList<Operator>)operatorHistory.clone();
	}
	
	@SuppressWarnings("unchecked")
	public ArrayList<LeafNode> cloneParsedLeafNodes()
	{
		return (ArrayList<LeafNode>)parsedLeafNodes.clone();
	}
	
	public String toTrace()
	{
		List<LTAGState> states = new ArrayList<LTAGState>();
		
		states.add(this);
		
		LTAGState previousState = getPreviousState();
		
		while (previousState != null)
		{
			states.add(0, previousState);
			
			previousState = previousState.getPreviousState();
		}
		
		return states.toString();
	}
	
	public ArrayKey getStatisticKey()
	{
		return getStateStatisticKey();
			
	}
	
	private ArrayKey getStateStatisticKey()
	{
		List<String> keyList = new ArrayList<String>(20);
		
		if (operatorHistory.size() == 0)
		{
			setListValue(keyList, tree.getRoot().getWord());
		}
		else
		{
			for (int i = 0;  i < parsedLeafNodes.size(); i++)
			{
				LeafNode leafNode = parsedLeafNodes.get(i);
				LTAGNode node = leafNode.getLeafNode();
				
				if (node.getWord() == null)
					continue;
				
				setListValue(keyList, node.getWord());
			}
		}
		
		return new ArrayKey(keyList.toArray(new Object[]{}));
	}
	
	private void setListValue(List<String> list, Word word)
	{
		int index = word.getWordIndex();
		
		while(list.size() <= index)
			list.add(null);
		
		list.set(index, word.getLexical());
	}
	
	public boolean operatorHistoryEquals(LTAGState state)
	{
		return Arrays.equals(getOperatorArray(), state.getOperatorArray());
	}
	
	@Override
	public int compareTo(LTAGState state) 
	{
		return Double.valueOf(freq).compareTo(state.getFreq());
	}
}
